# -*- coding: utf-8 -*-

"""剑指 Offer II 035. 最小时间差
给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：
输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：
输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：
2 <= timePoints <= 2 * 10^4
timePoints[i] 格式为 "HH:MM"""


class Solution:
    """按分钟计算，一天也就 24*60 = 1440 分钟，完全可以按分钟用桶排序。如果有重复的分钟数，直接返回0；
    后续在没有重复的分钟数的条件下，计算相邻两个时间点直接的间隔，因为分钟可以跨越天的界限，所以两个分钟时间的间隔应该有一对，为互补关系，
    再者因为跨天，最后一个时间还应该与第一个时间有相邻关系，有三种方案：
        1.建立循环链表（不可取，为了一个例外条件，将数组改为链表）；2.采用异常捕捉（自用）；3.将第一个时间点区间扩充到尾部，形成相邻关系（题解）"""
    def findMinDifference(self, timePoints) -> int:
        time_point_arr = [0 for _ in range(24*60)]
        for time_point in timePoints:
            minutes = int(time_point[0:2])*60+int(time_point[3:])
            if time_point_arr[minutes]:
                return 0
            else:
                time_point_arr[minutes] = 1
        
        start = 0
        while True:
            if time_point_arr[start]:
                break
            else:
                start += 1

        left = start
        right = start
        min_diff = 1440
        while True:
            try:
                right += 1
                if time_point_arr[right]:
                    diff = min(right-left, 1440-(right-left))
                    if diff == 1:
                        min_diff = 1
                        break
                    else:
                        min_diff = min(min_diff, diff)
                        left = right
            except IndexError:
                left, right = start, left
                min_diff = min(min_diff, min(right-left, 1440-(right-left)))
                break
        
        return min_diff


if __name__ == '__main__':
    so = Solution()
    print(so.findMinDifference(["23:59","00:00"]))
    print(so.findMinDifference(["00:00","23:59","00:00"]))
    print(so.findMinDifference(["01:01","02:01"]))
    print(so.findMinDifference(["00:00","04:00","22:00"]))
